import java.util.ArrayList;
import java.util.List;

/**
 * @author: shiding
 * @data: 2022/5/29 15:13
 * <p>
 * 19. 删除链表倒数第N个节点
 **/
public class RemoveNthFromEnd {


    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3 ,new ListNode(4, new ListNode(5)))));

    }

    /**
     * 暴利解法1 - 使用数组空间
     * 1、创建数组，将链表转换为数组
     * 2、获取 数组下标： 数组长度 - 倒数元素
     * 3、移除指定数组元素
     * 4、将数组 在遍历 转换成链表
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        ListNode temp2 = new ListNode(-1);
        ListNode out = temp2;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        int delkey = list.size() - n;
        list.remove(delkey);
        if (list != null || list.size() != 0) {
            for (int i : list) {
                temp2.next = new ListNode(i);
                temp2 = temp2.next;
            }
        }
        return out.next;
    }

    /**
     * 核心：还是使用快慢指针
     * 2、倒数第k个节点
     * 第一循环 快指针，先往前走k个节点
     * 第二次循环 快慢指针一走，当快指针走到链表尾部时
     * 慢指针刚好在 删除节点的 前一个节点上，则可以直接进行 改节点的 left.next = left.next.next
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode left = pre,right = pre;
        while (n != 0) {
            right = right.next;
            n--;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return pre.next;
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
